﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Pacman.Simulator;
using Pacman.Simulator.Ghosts;
using System.Diagnostics;
using PacmanAI.Graphs;

namespace PacmanAI
{

    class GhostProximityState 
    {
        Node[] _ghosts = new Node[4];
        public Node Pacman;
        int _proximity = -1;

        public int MaxProximityInFuture = int.MinValue;

        public GhostProximityState(Node newPac, GhostProximityState p)
        {
            Pacman = newPac;
            int i = 0;
            foreach (var g in p._ghosts)
            {
                 _ghosts[i++] = Closer(g); //4909
                // _ghosts[i++] = g; // 3485
            }
        }

        private Node Closer(Node n)
        {
            var r = n;
            foreach (var nn in n.PossibleDirections)
            {
                if (ProximityOf(nn) < ProximityOf(r))
                    r = nn;
            }
            return r;
        }

        public GhostProximityState(GameState gs)
        {
            Pacman = gs.Pacman.Node;
            int i = 0;
            foreach (var g in gs.Ghosts)
                _ghosts[i++] = g.Node;
        }

        public int ProximityOf(Node n)
        {
            if (Pacman == n)
                return 0;
            var r = Pacman.ShortestPath[n.X, n.Y];
            if (r == null)
             return int.MaxValue; // for some reason shorters paths are not all filled it
            else return r.Distance;
        }


        public int Proximity
        {
            get
            {
                if (_proximity == -1)
                {
                    _proximity = int.MaxValue;
                    foreach (var n in _ghosts)
                        _proximity =  IComparableExt.Minimum(_proximity, ProximityOf(n));
                }
                return _proximity;
            }
        }

        public override string ToString()
        {
            return string.Format("{0},{1}-{2},{3}", Pacman.X, Pacman.Y, Proximity, MaxProximityInFuture);
        }


    }

    class PathPlannerState : IGraphContent<PathPlannerState,Direction>
    {
        readonly Node[] _blockers;
        readonly Node[] _goals;
        public Node Pacman;
        int _proximity = -1;
        int _blockproximity = -1;

        public PathPlannerState(Node newPac, PathPlannerState p)
        {
            _blockers = p._blockers;
            _goals = p._goals;
            Pacman = newPac;
        }


        public PathPlannerState(GameState gs, Node[] goals, Node[] blockers)
        {
            Pacman = gs.Pacman.Node;
            _goals = goals;
            _blockers = blockers;
        }

        public int ProximityOf(Node n)
        {
            if (n == Pacman)
                return 0;
            var r = Pacman.ShortestPath[n.X, n.Y];
            if (r == null)
                return int.MaxValue;
            else return r.Distance;
        }


        public int Proximity
        {
            get
            {
                if (_proximity == -1)
                {
                    _proximity = int.MaxValue;
                    foreach (var n in _goals)
                        _proximity = IComparableExt.Minimum(_proximity, ProximityOf(n));
                }
                return _proximity;
            }
        }

        public int BlockProximity
        {
            get
            {
                if (_blockproximity == -1)
                {
                    _blockproximity = int.MaxValue;
                    foreach (var n in _blockers)
                        _blockproximity = IComparableExt.Minimum(_blockproximity, ProximityOf(n));
                }
                return _blockproximity;
            }
        }

        public override string ToString()
        {
            return string.Format("{0},{1}-{2}", Pacman.X, Pacman.Y, Proximity);
        }


        public void CollectSiblings(Graph<PathPlannerState, Direction>.Node path, Dictionary<Direction, PathPlannerState> siblings)
        {
            if (BlockProximity == 0  || Proximity == int.MaxValue || path.Depth == 30)
                return; 
            foreach (var nn in Pacman.GetPossibleDirections())
            {
                if (path.PathContains(
                    delegate(Graph<PathPlannerState, Direction>.Node e) { return e.Content.Pacman == nn; }))
                    continue;
                var sib = new PathPlannerState(nn, this);
                siblings[Pacman.GetDirection(nn)] = sib;
            }
        }


        public int DistanceFromGoal
        {
            get { return Proximity; }
        }
    }


    class ProximityGraph : Graphs.Graph<GhostProximityState, Direction>
    {
        // const int MAX_DEPTH = 10; // 4655
        const int MAX_DEPTH = 20; // 4909

        private void SetMax(Node n, int last)
        {
            if (n.Content.MaxProximityInFuture < last)
            {
                n.Content.MaxProximityInFuture = last;
            }
            if (!n.IsRoot)
                SetMax(n.Parent, last);
        }

        protected override void GetSiblings(
            PacmanAI.Graphs.Graph<GhostProximityState, Direction>.Node selected, 
            PacmanAI.Graphs.Graph<GhostProximityState, Direction>.NodeList frontier, 
            Dictionary<Direction, GhostProximityState> siblings)
        {
            if (selected.Depth == MAX_DEPTH)
                return; // no more siblings
            GhostProximityState s = selected.Content;
            if (s.Proximity == 0)
                return; // pacman is dead
            foreach (var nn in s.Pacman.GetPossibleDirections())
            {
                if (selected.PathContains(
                    delegate (Node e) { return e.Content.Pacman == nn; }))
                    continue;         
                
                var sib = new GhostProximityState(nn,s);
                siblings[s.Pacman.GetDirection(nn)] = sib;
                SetMax(selected, sib.Proximity);
            }
        }

        protected override bool IsGoal(PacmanAI.Graphs.Graph<GhostProximityState, Direction>.Node n)
        {
            return false;
        }
    }

    enum Behaviour { EatCarefully, RunAway, ChowThoseGosts, RunForPower }
    public delegate float NodeFunction(Node n);

    class HintMap
    {
        private float[,] _hintMap = new float[Map.Width, Map.Height];
        private Node _maxNode;
        public HintMap() { }

        /// <summary>
        /// Returns a value such the the higher value is more feasable
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>


        public void Recalculate(GameState gs, NodeFunction fn)
        {
            _maxNode = null;
            float maxValue = float.MinValue;

            for (int w = 0; w < Map.Width; w++)
                for (int h = 0; h < Map.Height; h++)
                {
                    if (gs.Pacman.X == w && gs.Pacman.Y == h)
                    {
                        _hintMap[w, h] = float.MinValue;
                        continue;
                    }
                    var n = gs.Map.Nodes[w, h];
                    if (n.Type == Node.NodeType.Wall)
                        _hintMap[w, h] = float.MinValue;
                    else
                    {
                        _hintMap[w, h] = fn(n);
                        var v = _hintMap[w, h];
                        if (_maxNode == null || v > maxValue)
                        {
                            _maxNode = n;
                            maxValue = v;
                        }
                    }
                }
        }

        /// <summary>
        /// The max value node since the last recalc
        /// </summary>
        public Node MaxNode { get { return _maxNode; } }

        public Direction HintedDirection(Pacman.Simulator.Pacman man)
        {
            Direction result = Direction.None;
            float maxV = float.MinValue;
            foreach (var d in man.PossibleDirections())
            {
                Node nd = man.Node.Beside(d);
                var v = _hintMap[nd.X, nd.Y];
                if (result == Direction.None || v > maxV)
                {
                    maxV = v;
                    result = d;
                }
            }
            return result;
        }


    }

    public class BehaveMan : BasePacman
    {

        private GameState _gs;
        private Behaviour _currentBehaviour = Behaviour.EatCarefully;
        private HintMap _hints = new HintMap();

        public BehaveMan() : base("BehaveMan", "1") { }

        private float WalkDistance(Node n1, Node n2)
        {
            var r = _gs.Map.GetRoute(n1, n2);
            if (r == null)
                return 0.0f;
            return r.Count;
        }

        private Direction NavigateTo(Node target)
        {
            var r = _gs.Map.GetRoute(_gs.Pacman.Node, target);
            if (r != null)
                return _gs.Pacman.Node.GetDirection(r[0]);
            else
                return Direction.None;
        }

        Node[] GhostChasingNodes()
        {

            var chasing = _gs.Ghosts.Filter(Ghost.MatchChasing);
            var r = new Node[chasing.Count];
            int i = 0;
            foreach (var g in chasing)
                r[i++] = g.Node;
            return r;
        }

        Node[] GhostEdibleNodes()
        {

            var chasing = _gs.Ghosts.Filter(Ghost.MatchEdible);
            var r = new Node[chasing.Count];
            int i = 0;
            foreach (var g in chasing)
                r[i++] = g.Node;
            return r;
        }

        SimpleGraph<PathPlannerState, Direction> _simpleGraph = new SimpleGraph<PathPlannerState, Direction>();
        private Direction SmartNavigateTo(Node target, Node[] avoids)
        {
            if (_simpleGraph.Search(
                new PathPlannerState(_gs, new Node[] { target },avoids)))
            {
                return _simpleGraph.GoalNode.ArchFromRoot();
            }
            else
            {
                //Debug.Print(_simpleGraph.ToString());
                return Direction.Stall;
            }
        }

        private Direction SmartNavigateTo(Node[] targets, Node[] avoids)
        {
            if (_simpleGraph.Search(
                new PathPlannerState(_gs, targets, avoids)))
            {
                return _simpleGraph.GoalNode.ArchFromRoot();
            }
            else
            {
                //Debug.Print(_simpleGraph.ToString());
                return Direction.Stall;
            }
        }

        private Behaviour CurrentBehaviour
        {
            get { return _currentBehaviour; }
            set
            {
                if (_currentBehaviour != value)
                {
                    // Debug.WriteLine(string.Format("{0} -> {1}", _currentBehaviour, value));
                    _currentBehaviour = value;
                }
            }
        }

        private Direction BehaviourResult()
        {
           // return StrategyRunAway();
            switch (_currentBehaviour)
            {
                case Behaviour.ChowThoseGosts:
                    return StrategyChowThoseGhosts();
                case Behaviour.EatCarefully:
                    return StrategyEatCarefully();
                case Behaviour.RunAway:
                    return StrategyRunAway();
                case Behaviour.RunForPower:
                    return StrategyRunForPower();
            }
            return Direction.None;
        }

        public override Direction Think(GameState gs)
        {
            _gs = gs;
            return BehaviourResult();
        }

        private Direction MaxDir(NodeFunction fn)
        {
            Direction result = Direction.None;
            float maxV = float.MinValue;
            foreach (var d in _gs.Pacman.PossibleDirections())
            {
                Node nd = _gs.Pacman.Node.Beside(d);
                var v = fn(nd);
                if (result == Direction.None || v > maxV)
                {
                    maxV = v;
                    result = d;
                }
            }
            return result;
        }


        private Direction StrategyRunForPower()
        {
            if (_gs.GhostsContains(Ghost.MatchEdible))
                return SwithBehaviour(Behaviour.ChowThoseGosts, "edible is close");

            int powerDist;
            Node powerPill;
            if (_gs.Map.TryFindClosestNode(_gs.Pacman.Node, Node.NodeType.PowerPill, out powerPill, out powerDist))
            {
                Ghost chasingGhost;
                int dist;
                if (_gs.TryFindClosestGhost(out chasingGhost, out dist) && dist < powerDist)
                {
                    return SwithBehaviour(Behaviour.RunAway, "chaser is close");
                }

                return SmartNavigateTo(powerPill, GhostChasingNodes());
            }
            return SwithBehaviour(Behaviour.EatCarefully, "no more power");
        }

        /// <summary>
        /// Higher value is less danger
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        private float DangerValue(Node n)
        {
            float value = 0.0f;
            foreach (Ghost g in _gs.Ghosts)
            {
                if (g.Chasing)
                    value += WalkDistance(g.Node, n);

            }
            if (n.Type == Node.NodeType.Pill)
                value += 0.5f;
            foreach (var p in _gs.Map.PowerPillNodes)
            {
                if (n.Type == Node.NodeType.PowerPill)
                    value += WalkDistance(p, n);
            }
            return value;
        }


        /// <summary>
        /// Higher value is further away from Ghosts
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        private float NoGhosts(Node n)
        {
            float value = 0.0f;
            foreach (Ghost g in _gs.Ghosts)
            {
                value += WalkDistance(g.Node, n);
            }
            return value;
        }


        private Direction SwithBehaviour(Behaviour newB, string reason)
        {
            Debug.Print(string.Format("{0} because {1}",newB, reason) );
            CurrentBehaviour = newB;
            _targetGhost = null;
            return Direction.None;
        }

        // ave 5466; 5221
        private Direction StrategyRunAway_sq()
        {
            Ghost chasingGhost;
            int dist;
            if (_gs.TryFindClosestGhost(out chasingGhost, out dist) && dist < SAFE_DISTANCE)
            {
                NodeFunction f = delegate(Node n)
                {
                    return n.DistanceSquaredTo(chasingGhost.Node);
                };
                return MaxDir(f);
            }
            else
                return SwithBehaviour(Behaviour.EatCarefully,"??");

        }


        private int CustomEscapeSafety(PathToObstacle p)
        {
            float w_power = 1,
                  w_pill = 1,
                  w_ghost = -2,
                  w_wall = 1,
                  w_sameDir = 1;
                  // w_length = 0.5f;  // weight per step

            int power = p.HasPowerPill ? 1 : 0;
            int pill = p.HasPill ? 1 : 0;
            int ghost = p.Obstacle == ObstacleType.Ghost ? 1 : 0;
            int wall = p.Obstacle == ObstacleType.Wall ? 1 : 0;
            int sameDir = p.Direction == _gs.Pacman.Direction ? 1 : 0;
            return (int) ((power * w_power
                + pill * w_pill
                + ghost * w_ghost
                + wall * w_wall
                + sameDir * w_sameDir)
                 * p.Length);
        }


        private int CustomEscapeSafety2(PathToObstacle p) // 7030
        {
            int offset = 0;
            if (p.Obstacle == ObstacleType.Ghost)
                offset -= 5;
            if (p.HasPowerPill)
                offset += 10;
            if (p.HasPill && p.Obstacle != ObstacleType.Ghost)
                offset += 10;
            if (p.Direction == _gs.Pacman.Direction && p.Obstacle != ObstacleType.Ghost)
                offset += 10; // safer to run in current dir
            return offset + p.Length;
        }

        private int CustomEscapeSafety1(PathToObstacle p) // 6300
        {
            int offset = 0;
            if (p.Obstacle == ObstacleType.Ghost)
                offset -= 5;
            if (p.HasPowerPill)
                offset += 10;
            if (p.HasPill && p.Obstacle != ObstacleType.Ghost)
                offset += 10;
            if (p.Direction == _gs.Pacman.Direction)
                offset += 5; // safer to run in current dir
            return offset + p.Length;
        }


        // 5407; 
        private Direction StrategyRunAway_lp()
        {
            Ghost chasingGhost;
            int dist;
            if (_gs.TryFindClosestGhost(out chasingGhost, out dist) && dist < SAFE_DISTANCE)
            {
                NodeFunction f = delegate(Node n)
                {
                    return n.DistanceSquaredTo(chasingGhost.Node);
                };
                var longest = _gs.Pacman.PossibleDirections().BestPath(
                    _gs.Pacman.Node,
                    _gs.Ghosts,
                    delegate(PathToObstacle a, PathToObstacle b)
                    { return CustomEscapeSafety(a) - CustomEscapeSafety(b); }
                    // PathToObstacle.CompareEscapeSafety // 4987
                    // PathToObstacle.CompareLengths // 4166
                    );
                return longest.Direction;
            }
            else
            {
                return SwithBehaviour(Behaviour.EatCarefully,"");
            }

        }

        // const int SAFE_DISTANCE = 15;  const int UNSAFE_DISTANCE = 10; 4594
        // const int SAFE_DISTANCE = 15; const int UNSAFE_DISTANCE = 15; // 44625
        // const int SAFE_DISTANCE = 10; const int UNSAFE_DISTANCE = 10; // 4397
        //const int SAFE_DISTANCE = 20; const int UNSAFE_DISTANCE = 20; // 4657
        //const int SAFE_DISTANCE = 18; const int UNSAFE_DISTANCE = 18; // 4795
        //const int SAFE_DISTANCE = 19; const int UNSAFE_DISTANCE = 17; // 4632
        //const int SAFE_DISTANCE = 19; const int UNSAFE_DISTANCE = 18; // 4695
        const int SAFE_DISTANCE = 18; const int UNSAFE_DISTANCE = 17; // 4886
        //const int SAFE_DISTANCE = 18; const int UNSAFE_DISTANCE = 16; // 4373
        const int PILL_COUNT_END = 100;
        ProximityGraph _graph = new ProximityGraph();
        private Direction StrategyRunAway()
        {
            Direction result;
            if (TrySwithToPowerSearch(out result))
                return result;
            Ghost chasingGhost;
            int dist;
            if (_gs.TryFindClosestGhost(out chasingGhost, out dist) && dist < SAFE_DISTANCE)
            {
                _graph.Search(new GhostProximityState(_gs), ProximityGraph.BreadthFirstSearch);
                if (_graph.Root.Siblings.Count == 0)
                    return Direction.None;
                var best = _graph.Root.Siblings[0];
                foreach (var s in _graph.Root.Siblings)
                    if (s.Content.MaxProximityInFuture > best.Content.MaxProximityInFuture)
                        best = s;
                //if (!_graph.Root.IsOnEdge)  Debug.WriteLine(_graph.ToString());
                return best.ArchFromParent;
            }
            else
            {
                return SwithBehaviour(Behaviour.EatCarefully,"ghosts far enough");
            }

        }

        int DistanceFromGhosts(Node n)
        {
            int result = 0;
            foreach (var g in _gs.Ghosts)
                if (IsChasing(g))
                    result += g.Node.DistanceSquaredTo(n);
            return result;
        }

        List<Node> WalkableNodes()
        {
            List<Node> result = new List<Node>();
            foreach (var n in _gs.Map.Nodes)
                if (n.Walkable)
                    result.Add(n);
            return result;
        }

        Node SafestNode()
        {
            return WalkableNodes().FindBest(
                delegate(Node a, Node b)
                {
                    int av = DistanceFromGhosts(a);
                    int bv = DistanceFromGhosts(b);
                    return bv.CompareTo(av);  // minimise distance
                });

        }




        private bool TrySwithToPowerSearch(out Direction d)
        {
            Node pill;
            int dist;
            if (_gs.Map.TryFindClosestNode(_gs.Pacman.Node, Node.NodeType.PowerPill, out pill, out dist)
                && dist < 15)
            {
                d = SwithBehaviour(Behaviour.RunForPower, "power pill is close");
                return true;
            }
            d = Direction.None;
            return false;
        }

        private bool IsEdible(Ghost g)
        {
            return g != null && g.Entered && !g.Chasing;
        }

        private bool IsChasing(Ghost g)
        {
            return g != null && g.Entered && g.Chasing;
        }


        private Direction StrategyEatCarefully()
        {
            Direction result = Direction.None;
            Node pill;
            Ghost g;
            int dist;
            if (_gs.TryFindClosestGhost(Ghost.MatchChasing, out g, out dist) && dist < UNSAFE_DISTANCE)
            {
                return SwithBehaviour(Behaviour.RunAway,"chasing ghost is too close");
            }

            if (_gs.TryFindClosestGhost(Ghost.MatchEdible, out g, out dist) && dist < UNSAFE_DISTANCE)
            {
                _targetGhost = g;
                return SwithBehaviour(Behaviour.ChowThoseGosts, "edible ghost is close");
            }

            // if (TrySwithToPowerSearch(out result))             return result;
            if (_gs.Map.TryFindClosestNode(_gs.Pacman.Node, Node.NodeType.Pill, out pill))
                return SmartNavigateTo(pill,GhostChasingNodes());
            if (_gs.Map.TryFindClosestNode(_gs.Pacman.Node, Node.NodeType.PowerPill, out pill))
                return SmartNavigateTo(pill,GhostChasingNodes());
            
            return Direction.None;
        }


        Ghost _targetGhost = null;
        private Direction StrategyChowThoseGhosts()
        {
            Ghost g;
            Node n;
            int dist;

            if (_gs.TryFindClosestGhost(out g, out dist))
                if (IsChasing(g))
                {
                    _targetGhost = null;
                    return SwithBehaviour(Behaviour.RunAway, "closest ghost is chaser");
                }

            if (_targetGhost != null && IsEdible(_targetGhost))
                return NavigateTo(_targetGhost.Node);

            if (_gs.Map.PillsLeft < PILL_COUNT_END)
            {
                return SwithBehaviour(Behaviour.EatCarefully, "close to end of maze");
            }

            return SmartNavigateTo(GhostEdibleNodes(), GhostChasingNodes());
            if (_gs.TryFindClosestGhost(Ghost.MatchEdible, out _targetGhost))
                return SmartNavigateTo(_targetGhost.Node,GhostChasingNodes());
            else
            {
                _targetGhost = null;
                return SwithBehaviour(Behaviour.RunForPower,"no ediable ghost");
            }
        }
    }
}
